/*
题目：从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
public class BuildTreeA {
    int preIndex = 0;//用于遍历前序数组，中序数组仅是工具人
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder, inorder, 0, preorder.length - 1);
    }

    private TreeNode dfs(int[] preorder, int[] inorder, int startIndex, int endIndex) {
        if (startIndex > endIndex) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int midIndex = searchNode(inorder, startIndex, endIndex, preorder[preIndex++]);
        root.left = dfs(preorder, inorder, startIndex, midIndex - 1);
        root.right = dfs(preorder, inorder, midIndex + 1, endIndex);
        return root;
    }

    private int searchNode(int[] inorder, int startIndex, int endIndex, int val) {
        for (int i = startIndex; i <= endIndex; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return 666;
    }
}
